#include "linearList.h"
#include <iostream>
using namespace std;

//构造函数
sequenceList::sequenceList(const int& a, const int& b, float arr[])
{
    maxCapcity=a;
    curNumberOfItem = b;
    myList = new float[maxCapcity];         //申请空间
    for (int i = 0; i < curNumberOfItem; i++)
        myList[i] = arr[i];      // 将所有数据元素设置为arr内的值
    
}

//析构函数
sequenceList::~sequenceList()
{
    delete[] myList;       //清除
}


//向表尾添加元素，不超过元素上限返回true,失败返回false
bool sequenceList::addItem(const float&num)
{
    if (curNumberOfItem + 1 > maxCapcity)      //注意：这里的cur和max都是不含0的
        return false;
    else
    {
        myList[curNumberOfItem] = num;
        curNumberOfItem++;
        return true;
    }
}

//在第i个位置后插入num
bool sequenceList::insertItem(const int& index, const float& num)
{
    if (index > curNumberOfItem || index<0)      
        return false;
    for (int j = curNumberOfItem-1; j >= index; j--)
    {
        myList[j+1] = myList[j];       //遍历，后移
    }
    curNumberOfItem++;              //记得加1
    myList[index] = num;
    return true;
}

//删除特定num元素
int sequenceList::deleteItem(const float& num)
{
    int pos = -1;
    for (int i = 0; i < curNumberOfItem ; i++)
    {
        if (myList[i] == num)
        {
            for (int j = i; j < curNumberOfItem-1; j++)
            {
                myList[j] = myList[j + 1];       //遍历左移
            }
            curNumberOfItem--;
            pos = i;
            break;
        }
    }
    return pos;
}

//成功返回true，值放在val中，失败返回false,查找序号为i的元素
bool sequenceList::locate(const int& i, float& val)
{
    if (i >= curNumberOfItem || i < 0)     //放在前面，以防访问越界
        return false;
    else
    {
        val = myList[i];
        return true;
    }
}

//按值查找 返回找到位置，找不到返回-1
int sequenceList::locate(const float& num)
{
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == num)
            return i;
    }
    return -1;
}

//倒序排列元素（使用原空间）
void sequenceList::reverse()
{
    for (int i = 0; i < curNumberOfItem/2; i++)
    {
        float temp = myList[i];
        myList[i] = myList[curNumberOfItem - i-1];
        myList[curNumberOfItem - i-1] = temp;
    }
}

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";
    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }
    cout << myList[curNumberOfItem-1] << endl;
}

//初始化链表
listNode::~listNode()
{

}

linkList::linkList(const int&a, float arr[])
{
    firstNode = curNode = lastNode = new listNode;
    listSize = a;
    for (int i = 0; i < a; i++)      //从左往右把自己遍历为last，其实是初始first
    {
        lastNode->next = new listNode;
        lastNode->next->data = arr[i];
        lastNode = lastNode->next;
    }
}

//无参建空链表
linkList::linkList()
{
    listSize = 0;
    firstNode = lastNode = new listNode;
    curNode = NULL;
}

//删除链表
linkList::~linkList()
{
    listNode* p;
    while (firstNode->next != NULL)
    {
        p = firstNode->next;
        delete(firstNode);        //遍历挨个删除，直到只剩头节点
        firstNode = p;
    }
    delete(firstNode);
}

//头插法，成功返回true，失败返回false
bool linkList::headInsertItem(const float& num)
{
    listNode* q=new listNode;
    if (q == NULL) return false;
    q->data = num;
    q->next = firstNode->next;
    firstNode->next = q;
    listSize++;
    return true;
}

//尾插法，成功返回true，失败返回false
bool linkList::tailInsertItem(const float& num)
{
    listNode* q = new listNode;
    if (q == NULL) return false;
    q->data = num;
    q->next = NULL;
    lastNode->next = q;
    lastNode = lastNode->next;       //千万不能忘qaq......lastNode不更新就读不到后面
    listSize++;
    return true;
}


//插入元素到index位置，成功返回插入位置，错误返回-1
int linkList::insertItem(const int& index, const float& num)
{
    if (index<0 || index>listSize) return -1;
    curNode = firstNode;
    for (int i = 0; i < index; i++)
        curNode = curNode->next;
    listNode* q = new listNode;
    if (q == NULL) return -1;
    q->data = num;
    q->next = curNode->next;
    curNode->next = q;
    listSize++;
    return index;

}

//返回删除位置，找不到返回-1
int linkList::deleteItem(const float& num)
{
    int index = 0;
    curNode = firstNode->next;
    listNode* q = firstNode;
    while (curNode->data != num && index < listSize)
    {
        curNode = curNode->next;
        q = q->next;
        index++;
    }
    if (curNode->data == num)
    {
        q->next = curNode->next;
        q = curNode;
        curNode = curNode->next;    //指针指向q的下一个，再释放q
        delete q;                  //这个函数中，q的唯一作用就是用于指向删除节点
        listSize--;
        return index;
    }
    return -1;
}


//查找元素，成功返回true，值放在val中，失败返回false
bool linkList::locate(const int& index, float& val)
{
    if (index<0 || index>listSize-1) return false;
    curNode = firstNode->next;
    for (int i = 0; i < index; i++)
        curNode = curNode->next;
    val = curNode->data;
    return true;
}


//返回找到位置，找不到返回-1
int linkList::locate(const float& num)
{
    curNode = firstNode->next;
    for (int i = 0; i < listSize; i++)
    {
        if (curNode->data == num)
        {
            return i;
        }
        curNode = curNode->next;
    }
    return -1;
}


//递增排序
void linkList::ascendingOrder()
{
    for (listNode* p = firstNode->next;p!=NULL;p=p->next)
    {
        for (listNode* q=p; q != NULL; q = q->next)
        {
            if (p->data > q->data)
            {
                float temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
        }
    }
}

//倒序排列元素
void linkList::reverse()
{
    listNode* p =firstNode->next;
    lastNode = p;
    firstNode->next = NULL;    //这个不能忘，否则第一个头插的节点没有next可指
    while (p != NULL)
    {
        curNode = p;
        p = p->next;
        curNode->next = firstNode->next;
        firstNode->next = curNode;
    }
}

//链表打印
void linkList::print()
{
    curNode = firstNode;
    cout << listSize << ":";
    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        curNode = curNode->next;
    }
}

void merge(linkList&A, linkList&B)           //此处直接用指针a尾接b头会指针指向错误
{   
    B.curNode = B.firstNode->next;
    for (int i = 0; i < B.listSize; i++)
    {
        A.headInsertItem(B.curNode->data);
        B.curNode = B.curNode->next;
    }
    A.ascendingOrder();
    A.reverse();
}
 